#include "simple_suffix_array.h"

#include <iostream>
#include <boost/foreach.hpp>
#include <boost/tuple/tuple.hpp>
#include <algorithm>
using std::string;
using std::vector;




// alternative functions to those in the standard but which only provides
// one argument to the comparator (which holds the test value)
// test of more than are indicated by an additional boolean dummy value
namespace
{
	struct t_suffix_array_cmp
	{
		const string& search_buffer;
		const unsigned tuple_size;
		t_suffix_array_cmp(const string& search_buffer_, unsigned tuple_size_): 
			search_buffer(search_buffer_), 
			tuple_size(tuple_size_){}
		bool operator() (unsigned a, unsigned b)
		{
			for (unsigned i = 0; i < tuple_size; ++i)
			{
				if (search_buffer[a + i] == search_buffer [b + i])
					continue;
				return search_buffer[a + i] < search_buffer [b + i];
			}
	
			// tuples are the same, sort in position order
			return a < b;
		}
	};




	using namespace std;
	template<typename ForwardIterator, typename Compare>
	ForwardIterator
	my_upper_bound(ForwardIterator first, ForwardIterator last,
				   Compare comp)
	{
		typedef typename iterator_traits<ForwardIterator>::value_type
		ValueType;
		typedef typename iterator_traits<ForwardIterator>::difference_type
		DistanceType;

		DistanceType len = std::distance(first, last);
		DistanceType half;
		ForwardIterator middle;

		while (len > 0)
		{
			half = len >> 1;
			middle = first;
			std::advance(middle, half);
			if (comp(*middle))
				len = half;
			else
			{
				first = middle;
				++first;
				len = len - half - 1;
			}
		}
		return first;
	}



	template<typename ForwardIterator, typename Compare>
	ForwardIterator
	my_lower_bound(ForwardIterator first, ForwardIterator last,
				   Compare comp)
	{
		typedef typename iterator_traits<ForwardIterator>::value_type
		ValueType;
		typedef typename iterator_traits<ForwardIterator>::difference_type
		DistanceType;

		// concept requirements

		DistanceType len = std::distance(first, last);
		DistanceType half;
		ForwardIterator middle;

		while (len > 0)
		{
			half = len >> 1;
			middle = first;
			std::advance(middle, half);
			if (comp(*middle, true))
			{
				first = middle;
				++first;
				len = len - half - 1;
			}
			else
				len	= half;
		}
		return first;
	}

	template<typename ForwardIterator, typename Compare>
	pair<ForwardIterator, ForwardIterator>
	my_equal_range(ForwardIterator first, ForwardIterator last,
				   Compare comp)
	{
		typedef typename iterator_traits<ForwardIterator>::value_type
		ValueType;
		typedef typename iterator_traits<ForwardIterator>::difference_type
		DistanceType;

		// concept requirements

		DistanceType len = std::distance(first, last);
		DistanceType half;
		ForwardIterator middle, left, right;

		while (len > 0)
		{
			half = len >> 1;
			middle = first;
			std::advance(middle, half);
			if (comp(*middle, true))
			{
				first = middle;
				++first;
				len = len - half - 1;
			}
			else if (comp(*middle))
				len = half;
			else
			{
				left = my_lower_bound(first, middle, comp);
				std::advance(first, len);
				right = my_upper_bound(++middle, first, comp);
				return pair<ForwardIterator, ForwardIterator>(left, right);
			}
		}
		return pair<ForwardIterator, ForwardIterator>(first, first);
	}


	struct t_find_in_suffix_array
	{
		t_find_in_suffix_array( const string& search_buffer_,
								const string& search_tuple_,
								unsigned tuple_size_,
								unsigned beg_pos_):
				search_tuple(search_tuple_), search_buffer(search_buffer_), 
				beg_pos(beg_pos_),
				tuple_size(tuple_size_)
		{
		}
	
		const string& search_tuple;
		const string& search_buffer;
		const unsigned beg_pos;
		const unsigned tuple_size;
		bool operator ()(unsigned b)
		{
			for (unsigned i = 0; i < tuple_size; ++i)
			{
				if (search_tuple[i + beg_pos] == search_buffer [b + i])
					continue;
				return search_tuple[i + beg_pos] < search_buffer [b + i];
			}
	
			// tuples are the same, sort in position order
			return false;
		}
		bool operator ()(unsigned b, bool)
		{
			for (unsigned i = 0; i < tuple_size; ++i)
			{
				if (search_tuple[i + beg_pos] == search_buffer [b + i])
					continue;
				return search_tuple[i + beg_pos] > search_buffer [b + i];
			}
	
			// tuples are the same, sort in position order
			return false;
		}
	};


}






t_simple_suffix_array::t_simple_suffix_array(const string& search_buffer_, const unsigned tuple_size_)
	: search_buffer(search_buffer_), tuple_size(tuple_size_)
{
	// pointers to various positions
	pos.reserve(search_buffer.length());
	for (unsigned i = 0; i < search_buffer.length() - tuple_size; ++i)
		pos.push_back(i);
	t_suffix_array_cmp suffix_array_cmp(search_buffer, tuple_size);
	// sort by first tuple_size characters
	sort(pos.begin(),  pos.end(), suffix_array_cmp);
}


unsigned t_simple_suffix_array::find_first_of(	const string&	search_tuple, 
												unsigned		search_buffer_beg_pos, 
												unsigned		search_buffer_end_pos, 
												unsigned		search_tuple_beg_pos,
												unsigned		search_tuple_end_pos)
{
	typedef vector<unsigned>::const_iterator citer;
	citer beg, end;
	unsigned search_size = _find(	search_tuple, 
									search_buffer_beg_pos, 
									search_buffer_end_pos, 
									search_tuple_beg_pos,
									search_tuple_end_pos,
									beg,
									end);

	// not found
	if (beg == end)
		return std::string::npos;


	// search string shorter than initial tuple, have to search all matches
	// and find earliest instance
	if (search_size < tuple_size)
	{
		unsigned min_val = std::string::npos;
		while (beg != end)
		{
			if (*beg == search_buffer_beg_pos)
				return search_buffer_beg_pos;
			if (*beg > search_buffer_beg_pos && 
				*beg < search_buffer_end_pos && 
				*beg < min_val)
				min_val = *beg;
			++beg;
		}
		return min_val;
	}

	
	// 
	// results are sorted in terms of position, 
	// just find the first one between
	// search_buffer_beg_pos and search_buffer_end_pos
	//  
	beg = std::lower_bound(beg, end, search_buffer_beg_pos);
	if (beg == end || *beg > search_buffer_end_pos)
		return std::string::npos;

	return *beg;
}



unsigned t_simple_suffix_array::_find(	const string&	search_tuple, 
									unsigned		search_buffer_beg_pos, 
									unsigned&		search_buffer_end_pos, 
									unsigned		search_tuple_beg_pos,
									unsigned&		search_tuple_end_pos,
									vector<unsigned>::const_iterator& results_beg,
									vector<unsigned>::const_iterator& results_end)
{
	// defined search areas
	if (search_tuple_end_pos == std::string::npos)
		search_tuple_end_pos = search_tuple.length();
	if (search_buffer_end_pos == std::string::npos)
		search_buffer_end_pos = search_buffer.length();

	unsigned search_tuple_len = search_tuple_end_pos - search_tuple_beg_pos;

	unsigned search_size = std::min(tuple_size, search_tuple_len);



	// the search space is not large enough to hold the entire tuple
	// ignore
	if (search_buffer_end_pos - search_buffer_beg_pos < search_size )
	{
		results_beg = results_end = pos.end();
		return search_size;
	}
		
	search_buffer_end_pos -= search_size;

		
	
	boost::tie(results_beg, results_end) = my_equal_range(pos.begin(),  pos.end(), 
										  t_find_in_suffix_array(search_buffer, 
																 search_tuple, 
																 search_size,
																 search_tuple_beg_pos));
	return search_size;
}

unsigned t_simple_suffix_array::find_last_of(	const string&	search_tuple, 
												unsigned		search_buffer_beg_pos, 
												unsigned		search_buffer_end_pos, 
												unsigned		search_tuple_beg_pos,
												unsigned		search_tuple_end_pos)
{
	typedef vector<unsigned>::const_iterator citer;
	citer beg, end;
	unsigned search_size = _find(	search_tuple, 
									search_buffer_beg_pos, 
									search_buffer_end_pos, 
									search_tuple_beg_pos,
									search_tuple_end_pos,
									beg,
									end);
	// not found
	if (beg == end)
		return std::string::npos;

	// nothing less than this
	//if (search_buffer_end_pos == 0)
	//	return std::string::npos;

	// search string shorter than initial tuple, have to search all matches
	// and find earliest instance
	if (search_size < tuple_size)
	{
		unsigned max_val = 0;
		while (beg != end)
		{
			// largest possible value: short circuit and return
			if (*beg == search_buffer_end_pos - 1)
				return search_buffer_end_pos - 1;

			// save if larger starting position than previous
			if (*beg >= search_buffer_beg_pos && 
				*beg < search_buffer_end_pos && 
				*beg >= max_val)
				max_val = *beg;
			++beg;
		}
		return max_val;
	}

	
	// 
	// results are sorted in terms of position, 
	// just find the first one between
	// search_buffer_beg_pos and search_buffer_end_pos
	//  
	typedef std::vector<unsigned>::const_reverse_iterator riter;
	riter rbeg(beg);
	riter rend(end);
	riter tmp;
	tmp = std::lower_bound(rend, rbeg, search_buffer_end_pos,
		std::greater<unsigned>());
	if (tmp == rbeg || *tmp < search_buffer_beg_pos)
		return std::string::npos;
	return *tmp;
}

	

/*
int main (int argc, char *argv[])
{
	t_program_args args;
	try
	{
		if (!process_command_line_options(argc, argv, args))
			return 1;
		string search_buffer ("ACASDFAFJALKSFJLSAKGLSDASDFSDASDFSDSSDFASDFAFAFAF");
		t_simple_suffix_array suffix_array (search_buffer, 5);

		for (unsigned i = 0; i < search_buffer.length() +1; ++i)
		{
			unsigned res = suffix_array.find_earliest_instance("ASDF", i);
			if (res != std::string::npos)
				std::cerr
				<< res
				<< "\tstarting from " << i <<"=" << search_buffer.substr(res,  5) << "\n";
			else
				std::cerr
				<< "NONE\tstarting from " << i << "\n";
		}


	}
	catch (std::exception& e)
	{
		std_print_error(args.CERR(),  e.what());
		return 1;

	}
	return 0;






	cerr << "\n";
	cerr << string(10, '!') << "\nEverything worked!!\n";

	return 0;
}
*/
